package me.algo.tree;

import org.checkerframework.checker.units.qual.A;

import javax.sound.sampled.Line;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

/**
 * @author guozheng
 * @date 2024/4/27
 */
public class T13s {
    public static void main(String[] args) {

    }

    public static List<List<Integer>> levelOrder(Node root) {
        if (Objects.isNull(root)) {
            return new ArrayList<>();
        }
        List<List<Integer>> rtn = new ArrayList<>();
        LinkedList<Node> que = new LinkedList<>();
        que.addLast(root);
        while (!que.isEmpty()) {
            int size = que.size();
            List<Integer> line = new ArrayList<>();
            while (size > 0) {
                size--;
                Node node = que.removeFirst();
                line.add(node.val);
                if (Objects.nonNull(node.children)) {
                    for (Node child : node.children) {
                        que.addLast(child);
                    }
                }
            }
            rtn.add(line);
        }
        return rtn;
    }

    /**
     * 589. N 叉树的前序遍历
     * @param root
     * @return
     */
    public List<Integer> preorder(Node root) {
        List<Integer> rtn = new ArrayList<>();
        help(root, rtn);
        return rtn;
    }


    void help(Node root, List<Integer> rtn) {
        if (Objects.isNull(root)) {
            return;
        }
        rtn.add(root.val);
        for (Node child : root.children) {
            help(child, rtn);
        }
    }
}
